package Solutions

import (
	"container/heap"
	"sort"
)

type pq_ struct {
	sort.IntSlice
}

func (p *pq_) Push(v interface{}) {
	p.IntSlice = append(p.IntSlice, v.(int))
}

func (p *pq_) Pop() interface{} {
	item := p.IntSlice[len(p.IntSlice)-1]
	p.IntSlice = p.IntSlice[:len(p.IntSlice)-1]
	return item
}

func totalCost(costs []int, k int, candidates int) int64 {
	if len(costs) <= 2*candidates {
		sort.Ints(costs)
		ans := 0
		for i := 0; i < k; i++ {
			ans += costs[i]
		}
		return int64(ans)
	}
	l, r := candidates-1, len(costs)-candidates
	lSlice := make([]int, candidates)
	rSlice := make([]int, candidates)
	copy(lSlice, costs[:candidates])
	copy(rSlice, costs[r:])
	pLeft := pq_{
		IntSlice: lSlice,
	}
	pRight := pq_{
		IntSlice: rSlice,
	}
	heap.Init(&pLeft)
	heap.Init(&pRight)
	var ans = 0
	for i := 0; i < k; i++ {
		if len(pRight.IntSlice) == 0 {
			ans += heap.Pop(&pLeft).(int)
			continue
		}
		if len(pLeft.IntSlice) == 0 {
			ans += heap.Pop(&pRight).(int)
			continue
		}
		if pRight.IntSlice[0] < pLeft.IntSlice[0] {
			ans += heap.Pop(&pRight).(int)
			r--
			if r == l {
				r++
			} else {
				heap.Push(&pRight, costs[r])
			}
		} else {
			ans += heap.Pop(&pLeft).(int)
			l++
			if l == r {
				l--
			} else {
				heap.Push(&pLeft, costs[l])
			}
		}
	}
	return int64(ans)

}
